It is known in the wireless telecommunications art to scramble data through a process known as interleaving for transmitting the data from one communication station to another communication station. The data is then de-scrambled through a de-interleaving process at the receiving station.
In Third Generation Partnership Project (3G) wireless systems, a specific type of data interleaving for frequency division duplex (FDD) modems physical channel data is specified. Physical channel data in a 3G system is processed in words having a pre-defined bit size, which is currently specified as 32 bits per word.
Blocks of arbitrary numbers of sequential data bits contained within sequential data words are designated for communication over FDD physical channels. In preparing each data block for transmission over the channel, the data is mapped row by row to a matrix having a pre-determined number of columns. Preferably there are fewer columns than the number of bits in a word. Currently 30 columns are specified in 3G for physical channel interleaving of data bit blocks contained in 32 bit words.
For example, a mapping of a 310 data bit block contained as bits w0,0-w9,21 within ten 32-bit words w0-w9 to a thirty column matrix is illustrated in FIG. 1. The 310 data bit block is mapped to a 30 column matrix having 11 rows. Since the data block has a total of 310 bits, the last twenty of the columns, columns 10-29, include one fewer data bit then the first ten columns, 0-9.
Whether or not all of the matrix columns have bits of data mapped to them is dependent upon the number of bits in the block of data. For example, a block of 300 data bits would be mapped to a 30×10 matrix completely filling all the columns since 300 is evenly divisible by 30. In general, for mapping a block of T elements, the last r columns of a C column by N row matrix will only have data in N−1 rows where r=(C*N)−T and r<C.
After the data bits have been mapped to the interleaver matrix, the order of the columns is rearranged in a pre-defined sequence and the data bits are written to a new set of words w′ on a column by column sequential basis to define an interleaved data block of sequential bits w′#,# in a set of sequential words w′.
For example, the 310 bit block of data contained in words w0-w9 of FIG. 1 is selectively stored to words w′0-w′9, in accordance with the preferred interleaver column sequence as shown in FIGS. 2a, 2b. For the set of words, w0-w9, the corresponding interleaved block of ten words w′0-w′9 contain all of the 310 bits of data of the original words w0-w9 in a highly rearranged/scrambled order. As shown in FIG. 2a, interleaved word w′0 is formed of a sequence of bits from columns 0, 20 and 10 of FIG. 1. The correspondence of the bits w#,# from the original words w0-w9 to the bits w′0,0-w′0,31 of interleaved word w′0 is illustrated in FIG. 2b. 
Various processes may occur concerning the interleaved data before it is transmitted to a receiving station. For example, the bit size structure may be expanded M number of times. If the bit expansion is specified as six fold, each of the interleaved data bits for a block of physical channel data is expanded to a six bit element. Also, other processes can occur concerning the interleaved data between the transmitter and the receiving station's deinterleaver that make it appear to the receiver's deinterleaver that bit expansion has occurred even though no such bit expansion was performed in transmission processing. For example, a receiving station may sample a received signal using an A/D converter and descramble/dispread clip samples into symbols with the resulting value having a multi-bit representation. Each original interleaved bit from the transmitter then appears to have been expanded M number of times.
By way of example, the ten interleaved data words w′0-w′9 of the example of FIGS. 2a and 2b are expanded into a block of 59 words W′0-W′58 for transmission and/or during reception processing as reflected in FIG. 3. FIGS. 4a-4f illustrate an example of the correspondence of the interleaved bits w′0,0-w′0,31 of word w′0 to expanded interleaved six-bit elements T′0-T′31 of words W′0-W′5.
Since the element bit size does not evenly divide into the word bit size, some elements span two sequential words. For example, in FIGS. 4a and 4b, element T′5 is partially contained in word W′0 and partly contained in the next word W′1.
In the receiving station, after reception and processing, the received block of expanded interleaved elements, for example, the bit W′0,0-W′58,3 in the 59 words W′0-W′58, must be deinterleaved, i.e. descrambled, to reassemble the data in its original sequential form. It would be highly advantageous to provide a method and apparatus for deinterleaving of expanded column interleaved data blocks in a fast and efficient manner.